{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Reach a Position After Exactly k Steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #恰好移动 k 步到达某一位置的方法数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>正</strong> 整数 <code>startPos</code> 和 <code>endPos</code> 。最初，你站在 <strong>无限</strong> 数轴上位置 <code>startPos</code> 处。在一步移动中，你可以向左或者向右移动一个位置。</p>\n",
    "\n",
    "<p>给你一个正整数 <code>k</code> ，返回从 <code>startPos</code> 出发、<strong>恰好</strong> 移动 <code>k</code> 步并到达 <code>endPos</code> 的 <strong>不同</strong> 方法数目。由于答案可能会很大，返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>如果所执行移动的顺序不完全相同，则认为两种方法不同。</p>\n",
    "\n",
    "<p><strong>注意：</strong>数轴包含负整数<strong>。</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startPos = 1, endPos = 2, k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>存在 3 种从 1 到 2 且恰好移动 3 步的方法：\n",
    "- 1 -&gt; 2 -&gt; 3 -&gt; 2.\n",
    "- 1 -&gt; 2 -&gt; 1 -&gt; 2.\n",
    "- 1 -&gt; 0 -&gt; 1 -&gt; 2.\n",
    "可以证明不存在其他方法，所以返回 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startPos = 2, endPos = 5, k = 10\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在从 2 到 5 且恰好移动 10 步的方法。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= startPos, endPos, k &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-reach-a-position-after-exactly-k-steps](https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-reach-a-position-after-exactly-k-steps](https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2\\n3', '2\\n5\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        M = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dp(cur, k):\n",
    "            if abs(cur - endPos) > k:\n",
    "                return 0\n",
    "            if not k:\n",
    "                return cur == endPos\n",
    "            \n",
    "            return (dp(cur-1, k-1) + dp(cur+1, k-1)) % M\n",
    "        \n",
    "        \n",
    "        return dp(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        distance = abs(startPos - endPos)\n",
    "        if distance > k or (k - distance) % 2 != 0:\n",
    "            return 0\n",
    "\n",
    "        extra_steps = (k - distance) // 2\n",
    "        a = extra_steps\n",
    "        b = distance + extra_steps\n",
    "        return (factorial(a+b) // (factorial(a) * factorial(b))) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, a: int, b: int, k: int) -> int:\n",
    "        if a>b:\n",
    "            a,b=b,a\n",
    "        if b-a>k:\n",
    "            return 0\n",
    "        if (b-a)%2!=k%2:\n",
    "            return 0\n",
    "        return comb(k,(k-(b-a))//2)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 如果直接考虑的话，这个状态就是startpos,endpos,k三者决定的，但是我觉得是由二者的差值决定的。\n",
    "        # 当差值一定的情况下，构造k*k大小的dp就完全够用了\n",
    "        dp = [[0]*(k+1) for _ in range(k+1)]\n",
    "        \n",
    "        for j in range(1,len(dp[0])):\n",
    "            # 不一定是1，它的个数是左挑和又跳的组合，考虑组合数\n",
    "            if j%2 == 0:\n",
    "                dp[0][j] = math.comb(j,j//2)%(10**9+7)\n",
    "        \n",
    "        # 初始处理\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        for cha in range(1,len(dp)-1):\n",
    "            for j in range(cha+1,len(dp[0])):\n",
    "                dp[j-cha][j] = (dp[j-cha+1][j-1] + dp[j-cha-1][j-1])%(10**9+7)\n",
    "        \n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        if abs(startPos-endPos) > k:\n",
    "            return 0\n",
    "        return dp[abs(startPos-endPos)][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        d = abs(endPos - startPos) \n",
    "        if k < d or (k - d) % 2 != 0:\n",
    "            return 0 \n",
    "        mod = int(1e9 + 7)\n",
    "        x = (k - d) // 2 \n",
    "\n",
    "        f = []\n",
    "        for i in range( k+1):\n",
    "            f.append([0] * (i+1))\n",
    "            for j in range(i+1):\n",
    "                if j == 0 or j == i:\n",
    "                    f[i][j] = 1\n",
    "                else:\n",
    "                    f[i][j] = (f[i-1][j] + f[i-1][j-1]) % mod \n",
    "        \n",
    "        return f[k][x] \n",
    "    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        n=abs(endPos-startPos)\n",
    "        if n%2!=k%2:\n",
    "            return 0\n",
    "        if n>k:\n",
    "            return 0\n",
    "        r=(k-n)//2\n",
    "        if r==0:\n",
    "            return 1\n",
    "        mod=10**9+7\n",
    "        f=[[0 for _ in range(r+1)]for _ in range(k+1)]\n",
    "        for i in range(1,k+1):\n",
    "            f[i][1]=i\n",
    "        for i in range(1,r):\n",
    "            f[i][i]=1\n",
    "        for i in range(2,k+1):\n",
    "            for j in range(2,min(i+1,r+1)):\n",
    "                f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod\n",
    "        print(f)\n",
    "        return f[k][r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s - e) > k:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        dis = abs(s - e)\n",
    "        if dis + k & 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(d, u):\n",
    "            if u == d == 0:\n",
    "                return 1\n",
    "            if d < 0:\n",
    "                return dfs(-d, u)\n",
    "            if d > u:\n",
    "                return 0\n",
    "            return (dfs(d + 1, u - 1) + dfs(d - 1, u - 1)) % mod\n",
    "        res = dfs(dis, k)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        startPos=1000+startPos\n",
    "        endPos=1000+endPos\n",
    "        dp=[[0 for _ in range(startPos+k+2)] for _ in range(k+1)]\n",
    "        dp[0][startPos]=1\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(k):\n",
    "            for j in range(startPos-k,startPos+k+1):\n",
    "                dp[i+1][j]=(dp[i][j-1]+dp[i][j+1])%mod\n",
    "        if endPos>k+startPos:\n",
    "            return 0\n",
    "        return dp[k][endPos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # r=(e-s+k)//2\n",
    "        # l=(s-e+k)//2\n",
    "        MOD = 10 ** 9 + 7\n",
    "        N = 2010\n",
    "        M = 1010 \n",
    "        dp=[[0]*N for i in range(k)]\n",
    "        diff = abs(startPos - endPos)\n",
    "        s = 1000  \n",
    "        e = 1000 + diff\n",
    "        dp=[[0]*3005 for i in range(1005)]\n",
    "        dp[1][s+1] = 1 # 走一步到s+1的方法是:向右1步\n",
    "        dp[1][s-1] = 1 # 走一步到s-1的方法是:向左1步\n",
    "        for i in range(2,k+1):# 一共可以走k步\n",
    "            for j in range(s-k,s+k+1): # 可以到达的范围是【s-k,s+k】\n",
    "                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MOD\n",
    "\n",
    "\n",
    "\n",
    "        return dp[k][e]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos-startPos)>k:\n",
    "            return 0\n",
    "        if abs(endPos-startPos)==k:\n",
    "            return 1\n",
    "        else:\n",
    "            a=0\n",
    "            b=endPos-startPos+k\n",
    "            dp=[[0]*(2*k+1) for _ in range(k+1)]\n",
    "            #dp[i][j]为第i步到达数轴上j位置的方法数\n",
    "            dp[0][k]=1\n",
    "            if k>=2:\n",
    "                for m in range(-k,k+1,1):\n",
    "                    if m!=0:\n",
    "                        dp[0][m+k]=0\n",
    "            for i in range(1,k+1):\n",
    "                for j in range(-k+1,k,1):\n",
    "                    if j-1>=-k+1:\n",
    "                        dp[i][j+k]+=dp[i-1][j-1+k]\n",
    "                    if j+1<= k-1:\n",
    "                        dp[i][j+k]+=dp[i-1][j+1+k]\n",
    "        return dp[k][b]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        lower = min(startPos - k, endPos - k)\n",
    "        upper = max(startPos + k, endPos + k)\n",
    "        n = upper - lower + 1\n",
    "        dp = [[0] * (k + 1) for _ in range(n)]\n",
    "        dp[startPos - lower][0] = 1\n",
    "        for j in range(1, k + 1):\n",
    "            dp[0][j] = dp[1][j - 1]\n",
    "            dp[n - 1][j] = dp[n - 2][j - 1]\n",
    "            for i in range(1, n - 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i + 1][j - 1]\n",
    "        return dp[endPos - lower][k] % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(2005)] for _ in range(1005)]\n",
    "        target = abs(startPos - endPos) + 1001\n",
    "\n",
    "        mod = 1e9+7\n",
    "        dp[0][1001] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(1, 2002):\n",
    "                dp[i][j]= (dp[i-1][j-1] + dp[i-1][j+1]) % mod\n",
    "        return int(dp[k][target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, start: int, ed: int, k: int) -> int:\r\n",
    "        mod = 10**9 + 7\r\n",
    "        dp = [[0] * 3050 for _ in range(0, 3010)]\r\n",
    "        start += 1000\r\n",
    "        ed += 1000\r\n",
    "        dp[0][start] = 1\r\n",
    "        dp[1][start + 1] = 1\r\n",
    "        dp[1][start - 1] = 1\r\n",
    "        for i in range(1, k + 1):\r\n",
    "            for j in range(1, 3010):\r\n",
    "                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod\r\n",
    "        return dp[k][ed]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.cache = {}\n",
    "\n",
    "    def f(self, left1, left2, startPos) -> int:\n",
    "        result = None\n",
    "        key =\"{0}+{1}\".format(left1, left2)\n",
    "        if key in self.cache:\n",
    "            result = self.cache[key]\n",
    "        elif left2 < 1:\n",
    "            result = 0\n",
    "        elif left2 == 1 and (left1 == startPos + 1 or left1 == startPos - 1):\n",
    "            result = 1\n",
    "        else:\n",
    "            result = self.f(left1 - 1, left2 - 1, startPos) + self.f(\n",
    "                left1 + 1, left2 - 1, startPos)\n",
    "        self.cache[key] = result\n",
    "        return result\n",
    "\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        return self.f(endPos, k, startPos) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if re == 0:\n",
    "                return 1 if idx == endPos else 0\n",
    "            return (dfs(idx + 1, re - 1) + dfs(idx - 1, re - 1)) % kmod\n",
    "        \n",
    "        ans = dfs(startPos, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos - startPos) == k and k > 0:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        MOD = (10**9+7)\n",
    "        @cache\n",
    "        def dfs(index, step):\n",
    "            #print(index, step)\n",
    "            nonlocal ans\n",
    "            res = 0\n",
    "            if index == endPos and step == k:\n",
    "                #ans += 1\n",
    "                res += 1\n",
    "            for i in [-1, 1]:\n",
    "                if step + 1 <= k:\n",
    "                    res += dfs(index + i, step + 1)\n",
    "            return res % MOD\n",
    "        return dfs(startPos, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(endPos - startPos) == k and k > 0:\n",
    "            return 1\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(index: int, steps: int) -> int:\n",
    "            ans, mod = 0, 10 ** 9 + 7\n",
    "\n",
    "            if index == endPos and steps == k:\n",
    "                ans += 1\n",
    "            for s in [-1, 1]:\n",
    "                if steps + 1 <= k:\n",
    "                    ans += dfs(index + s, steps + 1)\n",
    "            \n",
    "            return ans % mod\n",
    "        \n",
    "        return dfs(startPos, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def df(n, k):\n",
    "            if n % 2 != k % 2:\n",
    "                return 0\n",
    "            if k < n:\n",
    "                return 0\n",
    "            if k == n:\n",
    "                return 1\n",
    "            \n",
    "            if n == 0:\n",
    "                return (df(1, k - 1) * 2) % (10**9+7)\n",
    "            else:\n",
    "                return (df(n - 1, k - 1) + df(n + 1, k - 1)) % (10**9+7)\n",
    "        a, b = min(startPos, endPos), max(startPos, endPos)\n",
    "        return df(b - a, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        smallest, biggest = endPos - k, endPos + k\n",
    "        d = [[-1 for _ in range(k + 10)] for _ in range(2 * k + 10)]\n",
    "\n",
    "        for i in range(2 * k + 10):\n",
    "            d[i][0] = 0\n",
    "\n",
    "        d[startPos - smallest][0] = 1\n",
    "\n",
    "        for step in range(1, k + 1):\n",
    "            for nums in range(1, 2 * k + 9):\n",
    "                d[nums][step] = d[nums - 1][step - 1] + d[nums + 1][step - 1]\n",
    "\n",
    "        return d[endPos - smallest][k] % int((10 ** 9 + 7))\n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        md = int(1e9 + 7)\n",
    "        dc = {}\n",
    "        def dfs(sp, ep, k):\n",
    "            v = '{}|{}|{}'.format(sp, ep, k)\n",
    "            if not k or k < abs(sp - ep) or (sp - ep) & 1 != k & 1:\n",
    "                return 0\n",
    "            if k == abs(sp - ep):\n",
    "                return 1\n",
    "            if dc.get(v):\n",
    "                return dc[v]\n",
    "            n1, n2 = dfs(sp - 1, ep, k - 1), dfs(sp + 1, ep, k - 1)\n",
    "            dc[v] = (n1 + n2) % md\n",
    "            return dc[v]\n",
    "        return dfs(startPos, endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        seen = {}\n",
    "        def func(d, k):    # 距离 d 且有 k 步的情况下的方案总数\n",
    "            if d > k:\n",
    "                return 0\n",
    "            if d == k:\n",
    "                return 1\n",
    "            if (d, k) not in seen:\n",
    "                if not d:\n",
    "                    res = 0 if k % 2 else func(1, k-1) * 2\n",
    "                else:\n",
    "                    res = func(d+1, k-1) + func(d-1, k-1)\n",
    "                seen[d, k] = res % mod\n",
    "            return seen[d, k]\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        return func(abs(startPos - endPos), k)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j or j < 0:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return 1 if i == 0 else 0\n",
    "            return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return dfs(abs(startPos - endPos), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [{x:0 for x in range(startPos-k, startPos+k+1)} for _ in range(k+1)]\n",
    "        dp[0][endPos] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for x in range(startPos-k+1, startPos+k):\n",
    "                dp[i][x] = dp[i-1][x-1] + dp[i-1][x+1]\n",
    "        return dp[k][startPos] % (10**9 + 7)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD= 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if startPos + k < endPos:\n",
    "            return 0\n",
    "        \n",
    "        if (k - endPos + startPos) & 1:\n",
    "            return 0\n",
    "        \n",
    "        left = (k - endPos + startPos) // 2\n",
    "        right = k - left\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        @cache\n",
    "        def helper(l, r):\n",
    "            if l == r == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if l:\n",
    "                res += helper(l - 1, r)\n",
    "            if r:\n",
    "                res += helper(l, r - 1)\n",
    "            return res % MOD\n",
    "        \n",
    "        return helper(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        s, e = min(startPos, endPos), max(startPos, endPos)\n",
    "        d = e - s\n",
    "        if k < d or (k - d) % 2 != 0:\n",
    "            return 0\n",
    "        l, r = d + (k - d) // 2, (k - d) // 2\n",
    "        mod = 10 ** 9 + 7\n",
    "        @ cache\n",
    "        def comb(m, n):\n",
    "            if n > m:\n",
    "                return 0\n",
    "            if n == 0 or n == m:\n",
    "                return 1\n",
    "            return (comb(m - 1, n - 1) + comb(m - 1, n)) % mod\n",
    "        return comb(l + r, r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (k - (endPos - startPos)) & 1 or k < abs(endPos - startPos):\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def f(m, n):\n",
    "            if n == 0 or n == m:\n",
    "                return 1\n",
    "            return (f(m - 1, n) % MOD + f(m - 1, n - 1) % MOD) % MOD\n",
    "\n",
    "        return f(k, (k - (endPos - startPos)) // 2 + (endPos - startPos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        end = abs(startPos - endPos)\n",
    "        if end > k or (k - end) & 1:\n",
    "            return 0\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def f(p: int, k: int) -> int:\n",
    "            \"\"\"位置 p, 剩余步数 k, 从 p 往 0 走\"\"\"\n",
    "            if abs(p) > k:\n",
    "                return 0\n",
    "            if k == 0 and p == 0:\n",
    "                return 1\n",
    "            return (f(p - 1, k - 1) + f(p + 1, k - 1)) % mod\n",
    "\n",
    "        return f(end, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 奇偶性\n",
    "        if (endPos - startPos) % 2 and k % 2 == 0:\n",
    "            return 0\n",
    "        if (endPos - startPos) % 2 == 0 and k % 2:\n",
    "            return 0\n",
    "        if (endPos - startPos) > k:\n",
    "            return 0\n",
    "        MOD = 1000000007\n",
    "        @cache\n",
    "        def dfs(i: int, now: int) -> int:\n",
    "            if abs(endPos - now) == (k - i):\n",
    "                return 1\n",
    "            if abs(endPos - now) > (k - i):\n",
    "                return 0\n",
    "            if i == k:\n",
    "                return int(now == endPos)\n",
    "            # 往左\n",
    "            res = dfs(i + 1, now - 1)\n",
    "            \n",
    "            # 往右\n",
    "            res += dfs(i + 1, now + 1) \n",
    "            return res % MOD\n",
    "        \n",
    "        return dfs(0, startPos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "        if (k-(endPos-startPos))%2!=0:\n",
    "            return 0\n",
    "        \n",
    "        ans=0\n",
    "        @cache\n",
    "        def dfs(i,r):\n",
    "            d=abs(endPos-i)\n",
    "            if r<d:\n",
    "                return 0\n",
    "           \n",
    "            if i==endPos and r==0:\n",
    "                return 1\n",
    "        \n",
    "            return (dfs(i-1,r-1)+dfs(i+1,r-1))%mod\n",
    "            \n",
    "        \n",
    "        return dfs(startPos,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(self, startPos, endPos, k):\n",
    "            if (startPos, k) in cache:\n",
    "                return cache[(startPos, k)]\n",
    "            result = 0\n",
    "            distance = abs(endPos - startPos)\n",
    "            if k < distance or ((k - distance) % 2 != 0):\n",
    "                return result\n",
    "            if k == distance:\n",
    "                return 1\n",
    "            result = result + dfs(self, startPos - 1, endPos, k - 1)\n",
    "            result = result + dfs(self, startPos + 1, endPos, k - 1)\n",
    "            cache[(startPos, k)] = result\n",
    "            return int(result % (10**9 + 7))\n",
    "\n",
    "        return dfs(self,startPos, endPos, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        y = k + endPos - startPos\n",
    "        x = k - endPos + startPos\n",
    "        if y & 1 or x & 1 or x < 0 or y < 0:\n",
    "            return 0\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        # print(x, y)\n",
    "        # return math.comb((x + y)//2, x//2) % MOD\n",
    "\n",
    "        # L R\n",
    "        # R - L = endPos - startPos\n",
    "        # R + L = k\n",
    "        # 2R = k + endPos -startPos \n",
    "        # 2L = k - endPos + startPos\n",
    "        # dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        @cache\n",
    "        def helper(i, j) -> int:\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if j == 0:\n",
    "                return 1\n",
    "            return helper(i-1, j) + helper(i, j-1)\n",
    "        return helper(x//2, y//2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def rec(n,m):\n",
    "            if m == n:\n",
    "                return 1\n",
    "            elif m == 1:\n",
    "                return n\n",
    "            else:\n",
    "                return rec(n-1,m-1)+rec(n-1,m)\n",
    "        n = endPos - startPos\n",
    "        if k < abs(n):\n",
    "            return 0\n",
    "        if k == abs(n):\n",
    "            return 1\n",
    "        if (k + n) % 2: \n",
    "            return 0\n",
    "        m = (k + n)//2\n",
    "        return  rec(k, m) % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def comb(k, b):\n",
    "            if b == 0 or b == k:\n",
    "                return 1\n",
    "            return comb(k -1, b) + comb(k - 1, b - 1)\n",
    "\n",
    "        a = abs(startPos - endPos)\n",
    "        if a > k:\n",
    "            return 0 \n",
    "        b = k - a \n",
    "        if b & 1:\n",
    "            return 0\n",
    "        return comb(k, b // 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[-1 for i in range(1001)] for j in range(3001)]\n",
    "        def dfs(pos,step):\n",
    "            if dp[pos+1000][step] > -1:\n",
    "                return dp[pos+1000][step]\n",
    "            if abs(pos-endPos) > step:\n",
    "                return 0\n",
    "            if step == 0:\n",
    "                return 1\n",
    "            dp[pos+1000][step] = (dfs(pos-1,step-1) + dfs(pos+1,step-1))%1000000007\n",
    "            return dp[pos+1000][step]\n",
    "        return dfs(startPos,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos, endPos, k):\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def f(x, left):\n",
    "            if abs(x - endPos) > left: return 0\n",
    "            if left == 0: return 1  # 成功到达终点，算一种方案\n",
    "            return (f(x - 1, left - 1) + f(x + 1, left - 1)) % MOD\n",
    "        return f(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        @cache\n",
    "        def dfs(i, step):\n",
    "            if abs(endPos - i) > step:\n",
    "                return 0\n",
    "            if step == 0:\n",
    "                return 1 \n",
    "            return (dfs(i-1,step-1) + dfs(i+1,step-1))%mod\n",
    "        return int(dfs(startPos,k) % mod)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # 想不到状态转移的办法\n",
    "        # 搜索\n",
    "\n",
    "        @cache\n",
    "        def dfs(start, end, res):\n",
    "\n",
    "            if abs(end - start) > res:\n",
    "                return 0\n",
    "\n",
    "            if res == 0:\n",
    "                return 1 if start == end else 0\n",
    "            return (dfs(start - 1, end, res - 1) + dfs(start + 1, end, res - 1)) % (1e9 + 7)\n",
    "        \n",
    "        return int(dfs(startPos, endPos, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @cache\n",
    "        def move(s, e, k):\n",
    "            dis = abs(e - s)\n",
    "            if dis == k:\n",
    "                return 1\n",
    "            if dis > k or dis % 2 == 0 and k % 2 == 1 or dis % 2 == 1 and k % 2 == 0:\n",
    "                return 0\n",
    "\n",
    "            return move(-1, dis, k - 1) + move(1, dis, k - 1)\n",
    "        \n",
    "        return move(0, endPos - startPos, k) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        #dp = [[0 for _ in range(k+1)] for _ in range(endPos+1)]\n",
    "        dp = defaultdict(int)\n",
    "        dp[startPos,0] = 1\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(startPos-k-1, startPos+k+2):\n",
    "                dp[j,i] = (dp[j-1,i-1] + dp[j+1,i-1]) % (10**9+7)\n",
    "        return dp[endPos,k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize=None)\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if k == 0 and startPos == endPos:\n",
    "            return 1 \n",
    "        if k<0:\n",
    "            return 0 \n",
    "        if abs(startPos-endPos)>k:\n",
    "            return 0 \n",
    "        return (self.numberOfWays(startPos-1, endPos, k-1) + self.numberOfWays(startPos+1, endPos, k-1)) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        m = 10**9+7\n",
    "        if abs(s-e)>k:\n",
    "            return 0\n",
    "        if abs(s-e)==k:\n",
    "            return 1\n",
    "        return (self.numberOfWays(s,e-1,k-1)+self.numberOfWays(s,e+1,k-1))%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @ cache\n",
    "        def dfs(x,l):\n",
    "            if abs(endPos-x) > l:\n",
    "                return 0\n",
    "            if l == 0:\n",
    "                return 1\n",
    "            return dfs(x-1,l-1)+dfs(x+1,l-1)\n",
    "        return dfs(startPos,k)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:    \n",
    "        @cache\n",
    "        def f(s,e,kk):\n",
    "            d=abs(s-e)\n",
    "            if d>kk:\n",
    "                return 0\n",
    "            # if d&1 !=kk&1:\n",
    "            #     return 0\n",
    "            if kk==0:\n",
    "                if s==e:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return f(s-1,e,kk-1)+f(s+1,e,kk-1)\n",
    "        return f(startPos,endPos,k)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(3001)] for _ in range(k + 1)]\n",
    "        startPos += 1000\n",
    "        endPos += 1000\n",
    "        res = 0 \n",
    "        @lru_cache(None)\n",
    "        def helper(startPos, k):\n",
    "            nonlocal res\n",
    "            if abs(startPos - endPos) == 1 and k == 1:\n",
    "                # print(k, startPos)\n",
    "                dp[k][startPos] += 1\n",
    "            elif k < 1:\n",
    "                return 0\n",
    "            else:\n",
    "                helper(startPos - 1, k - 1)\n",
    "                helper(startPos + 1, k - 1)\n",
    "                dp[k][startPos] = (dp[k-1][startPos - 1] + dp[k-1][startPos + 1])%(10**9+7)\n",
    "        helper(startPos, k)\n",
    "        return dp[k][startPos]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (endPos-startPos)>k or (endPos-startPos)&1 !=(k&1):\n",
    "            return 0\n",
    "        \n",
    "        MOD=10**9+7\n",
    "        @cache\n",
    "        def dfs(s,k):\n",
    "            if (endPos-s)>k :\n",
    "                return 0\n",
    "            if  k==0:\n",
    "                return 1 if s==endPos else 0\n",
    "            return dfs(s-1,k-1)%MOD+dfs(s+1,k-1)%MOD\n",
    "            \n",
    "        return dfs(startPos,k)%MOD\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        d = abs(startPos - endPos)\n",
    "        @cache\n",
    "        def get(x,l):\n",
    "            if x > l or l < 0:\n",
    "                return 0\n",
    "            if l == 0 and x == 0:\n",
    "                return 1\n",
    "            return (get(x+1, l-1) + get(x-1, l-1)) % MOD\n",
    "        return get(d,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, kk):\n",
    "            if abs(endPos - ii) > kk:\n",
    "                return 0\n",
    "            if abs(endPos - ii) == kk:\n",
    "                return 1\n",
    "\n",
    "            return (dp(ii-1, kk-1) + dp(ii+1, kk-1)) % 1000000007\n",
    "\n",
    "\n",
    "        return dp(startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # hash 存储记忆化的中间结果\n",
    "        memo = defaultdict(int)\n",
    "        # cur 3  d = 2   k =  3  end 6\n",
    "        # 记忆化搜索\n",
    "        # 当前距离为cur 已经走了d步 的方案数\n",
    "        # 写python 记忆化搜索一定要加个@cache 不然就会超时\n",
    "        @cache\n",
    "        def dfs(cur: int, d: int) -> int:\n",
    "            if k - d  < abs(endPos - cur):\n",
    "                return 0\n",
    "            if d == k:\n",
    "                return 1\n",
    "            # 这个key的赋值 是整个记忆化里最关键的一步\n",
    "            # key包含cur 以及 d 两个信息\n",
    "            # 如果只是从0开始 这两个信息可能会其冲突 比如 你cur = 3 可能只是向右了3步 但也可能是向右6步后折返了3步 即会产生哈希冲突\n",
    "            # 由于题目条件是最多走1000步 所以只要cur* 比1000大的数 不同的key之间就不会存在冲突了 \n",
    "            key = cur * 1005 + d\n",
    "            # 已经搜索过直接返回\n",
    "            if memo.get(key):\n",
    "                return memo[key]\n",
    "            v = (dfs(cur + 1, d + 1) + dfs(cur - 1, d + 1)) % MOD\n",
    "            memo[key] = v\n",
    "            return v\n",
    "\n",
    "        return dfs(startPos, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(pos, k):\n",
    "            if k<0:\n",
    "                return 0\n",
    "            if abs(pos-startPos) == k:\n",
    "                return 1\n",
    "            \n",
    "            return dp(pos+1, k-1)+dp(pos-1, k-1)\n",
    "        \n",
    "        return dp(endPos, k)%1000000007\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, sp: int, ep: int, k: int) -> int:\n",
    "        dis = ep - sp\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(d, k):\n",
    "            if d == k:\n",
    "                return 1\n",
    "            if k <= 0:\n",
    "                return 0\n",
    "            ans = dp(d+1, k-1) + dp(d-1, k-1)\n",
    "            return ans % mod\n",
    "        \n",
    "        return dp(abs(dis), k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s-e) > k:\n",
    "            return 0\n",
    "        elif (e-s + k) & 1:\n",
    "            return 0\n",
    "        elif abs(s-e) == k:\n",
    "            return 1\n",
    "        else:\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(n, k):\n",
    "                if k == 0: return n == 0\n",
    "                return (dfs(n-1, k-1) + dfs(n+1, k-1)) % (10**9+7)\n",
    "            return dfs(e-s, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dis = s - e if s >=e else e - s\n",
    "        if (k < dis) or (k - dis) % 2 == 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(c: int, p: int, k: int) -> int:\n",
    "            if(k < abs(c-e)):\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return int(c == e)\n",
    "            ans = 0\n",
    "            ans += dfs(c-1, c, k-1)\n",
    "            ans %= mod\n",
    "            ans += dfs(c+1, c, k-1)  \n",
    "            ans %= mod\n",
    "            return ans\n",
    "        res = dfs(s,s - k,k)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        s = startPos\n",
    "        e = endPos\n",
    "        d = e-s \n",
    "        if k < d:\n",
    "            return 0\n",
    "        elif (k-d) % 2 == 1:\n",
    "            return 0\n",
    "        p = (k-d)//2 # 可以有 p 次的折返\n",
    "\n",
    "        l = s-p\n",
    "        r = e+p\n",
    "        # print(l, r)\n",
    "        '''\n",
    "        l l+1 l+2 ... s-1 s s+1 s+2 ... e-1 e e+1 ... r-1 r\n",
    "                          ^                 ^\n",
    "        0 1 2 3\n",
    "          - - -\n",
    "        '''\n",
    "        ## dp\n",
    "        cache = {}\n",
    "        def dp(i=s, k=k):\n",
    "            if (i, k) in cache:\n",
    "                return cache[(i, k)]\n",
    "            if k == 0:\n",
    "                if i == e:\n",
    "                    return 1 \n",
    "                return 0\n",
    "            elif k < 0:\n",
    "                return 0\n",
    "            if i == l:\n",
    "                res = dp(i+1, k-1)\n",
    "            elif i == r:\n",
    "                res = dp(i-1, k-1)\n",
    "            else:\n",
    "                res = dp(i+1, k-1) + dp(i-1, k-1)\n",
    "            cache[(i, k)] = res\n",
    "            return res \n",
    "\n",
    "        res = dp(s, k)\n",
    "        res = int(res%1000000007)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int, MOD = 10**9 + 7) -> int:\n",
    "        @cache\n",
    "        def dfs(n, k):\n",
    "            if n > k: return 0\n",
    "            if k == 0: return n == 0\n",
    "            return (dfs(n + 1, k - 1) + dfs(n - 1, k - 1)) % MOD\n",
    "        return dfs(endPos - startPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(i, j, k):\n",
    "            if j-i > k:\n",
    "                return 0\n",
    "            if j-i == k:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            return (f(i-1, j, k-1)+f(i+1, j, k-1))%MOD\n",
    "        return f(startPos, endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if (k - (endPos - startPos)) % 2 != 0 or (k - (endPos - startPos)) < 0: return 0\n",
    "        if k == endPos - startPos: return 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, step):\n",
    "            if pos == endPos and step == 0: return 1\n",
    "            if step == 0: return 0\n",
    "            return dfs(pos + 1, step - 1) + dfs(pos - 1, step - 1)\n",
    "        return dfs(startPos, k) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        e = abs(startPos - endPos)\n",
    "        if e > k or (k - e) & 1:\n",
    "            return 0\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def f(k: int, p: int) -> int:\n",
    "            '''位置 p, 剩余步数 k'''\n",
    "            if k < 0:\n",
    "                return 0\n",
    "            if k == 0 and p == 0:\n",
    "                return 1\n",
    "            return (f(k - 1, p - 1) + f(k - 1, p + 1)) % mod\n",
    "\n",
    "        return f(k, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        if abs(s-e) > k:\n",
    "            return 0\n",
    "        elif (e-s + k) & 1:\n",
    "            return 0\n",
    "        else:\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(n, k):\n",
    "                if k == 0: return n == 0\n",
    "                return (dfs(n-1, k-1) + dfs(n+1, k-1)) % (10**9+7)\n",
    "            return dfs(e-s, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, s: int, e: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(cur, rem):\n",
    "            if rem > k : return 0\n",
    "            if cur == e and rem == k: return 1\n",
    "            if cur + k - rem < e: return 0\n",
    "            return (dfs(cur - 1, rem + 1) + dfs(cur + 1, rem + 1)) % mod\n",
    "        \n",
    "        return dfs(s, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        # dfs\n",
    "        # 枚举向左/向右挪动相应的步数，到达某个位置的方法数\n",
    "        @cache\n",
    "        def dfs(cur_pos, step, k, endPos):\n",
    "            if step == k:\n",
    "                if cur_pos == endPos:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            # 剪枝 - 跳k步跳不到终点，及时返回\n",
    "            if abs(endPos-cur_pos) > k:\n",
    "                return 0\n",
    "\n",
    "            # 向左挪动一步\n",
    "            l_methods = dfs(cur_pos-1, step+1, k, endPos)\n",
    "            l_methods = l_methods % self.MOD\n",
    "            # 向右挪动一步\n",
    "            r_methods = dfs(cur_pos+1, step+1, k, endPos)\n",
    "            r_methods = r_methods % self.MOD\n",
    "            return (l_methods + r_methods) % self.MOD\n",
    "\n",
    "\n",
    "        # 排除一些肯定不满足条件的case\n",
    "        if k % 2 == 0:\n",
    "            if startPos % 2 != endPos % 2:\n",
    "                return 0\n",
    "        else:\n",
    "            if startPos % 2 == endPos % 2:\n",
    "                return 0\n",
    "        self.MOD = 10 ** 9 + 7\n",
    "        return dfs(startPos, 0, k, endPos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        dis = endPos - startPos\n",
    "        if dis > k:\n",
    "            return 0\n",
    "        if dis == k:\n",
    "            return 1\n",
    "        @cache\n",
    "        def dfs(cur: int, kk: int) -> int:\n",
    "            if endPos - cur > kk:\n",
    "                return 0\n",
    "            elif endPos - cur == kk:\n",
    "                return 1\n",
    "            elif kk == 0:\n",
    "                return 0\n",
    "            return dfs(cur - 1, kk - 1) + dfs(cur + 1, kk - 1)\n",
    "        return dfs(startPos, k) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(startPos-endPos-k)%2:return 0\n",
    "        @cache\n",
    "        def helper(dist,n):\n",
    "            if n==0:return 1 if dist==0 else 0\n",
    "            return helper(dist-1,n-1)+helper(dist+1,n-1)\n",
    "        return helper(abs(endPos-startPos),k)%int(10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, rest):\n",
    "            if abs(cur - endPos) > k:\n",
    "                return 0\n",
    "            if rest < 0:\n",
    "                return 0\n",
    "            if rest == 0:\n",
    "                return 1 if cur == endPos else 0\n",
    "            else:\n",
    "                res = 0\n",
    "\n",
    "                # 向左向右分别枚举\n",
    "                res += dfs(cur + 1, rest - 1)\n",
    "                res += dfs(cur - 1, rest - 1)\n",
    "                return res % mod\n",
    "        \n",
    "        return dfs(startPos, k) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        from functools import cache\n",
    "        MOD = 1000000000 + 7\n",
    "        @cache\n",
    "        def recur(pos, k):\n",
    "            if abs(pos - startPos) > 1010:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                if pos == startPos:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return (recur(pos - 1, k - 1) + recur(pos + 1, k - 1)) % MOD\n",
    "        return recur(endPos, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if abs(startPos - endPos) == k:\n",
    "            return 1\n",
    "        \n",
    "        if abs(startPos - endPos) > k:\n",
    "            return 0\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos, steps):\n",
    "            if steps == k:\n",
    "                if pos == endPos:\n",
    "                    return 1\n",
    "                return 0\n",
    "            \n",
    "            return (dfs(pos + 1, steps + 1) + dfs(pos - 1, steps + 1)) % 1000000007\n",
    "        \n",
    "        return dfs(startPos, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(start, end, k):\n",
    "    if k == 0 and end == start:\n",
    "        return 1\n",
    "    elif k == 0 and end != start:\n",
    "        return 0\n",
    "\n",
    "    # print(dfs(start, end - 1, k - 1) , dfs(start, end - 1, k - 1))\n",
    "    return (dfs(start, end - 1, k - 1) + dfs(start, end + 1, k - 1)) % (1000000007)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "\n",
    "        return dfs(startPos, endPos, k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if startPos < endPos - k or startPos > endPos + k :\n",
    "            return 0 \n",
    "        \n",
    "        memo = {}\n",
    "        def dfs(index, move):\n",
    "            if (index, move) in memo:\n",
    "                return memo[(index, move)]\n",
    "            if move > k:\n",
    "                return 0\n",
    "            if move == k:\n",
    "                if index == endPos:\n",
    "                    return 1\n",
    "                return 0 \n",
    "            val = 0 \n",
    "            if index + 1 <= endPos + k and index + 1 >= endPos - k :\n",
    "                val += dfs(index+1, move + 1)\n",
    "            if index - 1 <= endPos + k and index - 1 >= endPos - k :\n",
    "                val += dfs(index-1, move + 1)\n",
    "            memo[(index, move)] = val % mod\n",
    "            return memo[(index, move)]  \n",
    "        ans = dfs(startPos, 0)\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @cache\n",
    "    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "\n",
    "        if endPos - startPos == k:\n",
    "            return 1\n",
    "        elif endPos - startPos > k:\n",
    "            return 0\n",
    "        else:\n",
    "            return (self.numberOfWays(startPos + 1, endPos, k - 1) + self.numberOfWays(startPos - 1, endPos, k - 1))%int(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, start: int, end: int, k: int) -> int:\n",
    "        if start>end:\n",
    "            start,end=end,start\n",
    "            \n",
    "        mod=10**9+7\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos,left):\n",
    "            if left==0:\n",
    "                return int(pos==end)\n",
    "            \n",
    "            ans=0\n",
    "            # if abs(end-pos)>left:return 0\n",
    "            ans+=dfs(pos+1,left-1)\n",
    "            ans+=dfs(pos-1,left-1)\n",
    "            return ans%mod\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(start,k)%mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
